package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：33. 搜索旋转排序数组
 * 这道题考的是时间复杂度 如果遍历查找的话时间复杂度是 O(n) 题目要求O(log n)
 * <p>
 * 需要利用数组本身的有序性
 * 二分查找 拆分出来的两个数组肯定有一个是有序的  一个是部分有序的 如果值不在有序部分 则在部分有序里面重复相同操作 直到找到或者数组遍历完成为止
 *
 * 判断哪边是有序的 只需要比较中间节点与末端节点(或首端节点)的大小即可
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-09 10:17
 */
public class Search {
    public static void main(String[] args) {

        int[] nums = {3, 5, 1};
        System.out.println(search2(nums, 3, 0, nums.length - 1));
    }

    public static int search2(int[] nums, int target, int start, int end) {
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else if (end - start <= 1) {
            return -1;
        }
        //比较中间节点与末端节点的大小 如果大于 则说明左边是顺序 否则右边是顺序
        int index = (start + end + 1) / 2;
        if (nums[index] == target) {
            return index;
        }
        if (nums[index] > nums[end]) {
            //左边是顺序
            if (target >= nums[0] && target < nums[index]) {
                //说明 数值在左边 二分查找
                return binarySearch(nums, target, start, index);
            } else {
                //否则在右边
                return search2(nums, target, index, end);
            }
        } else {
            //右边是顺序
            if (target <= nums[end] && target >= nums[index]) {
                //说明 数值在右边 二分查找
                return binarySearch(nums, target, index, end);
            } else {
                //否则在左边
                return search2(nums, target, start, index);
            }
        }
    }

    public static int binarySearch(int[] nums, int target, int start, int end) {
        //二分查找
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else if (end - start <= 1) {
            return -1;
        }

        int index = (start + end + 1) / 2;
        if (target == nums[index]) {
            return index;
        }
        if (target > nums[index]) {
            return binarySearch(nums, target, index, end);
        } else {
            return binarySearch(nums, target, start, index);
        }
    }
}
